本篇同步發布於Blog: [解題] LeetCode - 376 Wiggle Subsequence

平台：

LeetCode

題號：

376 - Wiggle Subsequence

題目連結：

https://leetcode.com/problems/wiggle-subsequence/

題目說明：

        輸入一個數字序列，求有最長長度的擺動子序列(Wiggle Subsequence)，並輸出此原始序列的長度。擺動序列的定義為原本序列是[a, b, c, d, .... x]，而它們的相差序列[b - a, c - b, d - c, ...., x - w]裡的元素都是以正和負交替呈現。

　　比如範例輸入的[1,7,4,9,2,5]，相差序列為[6,-3,5,-7,3]，符合擺動序列的規則，也是最長的擺動子序列，所以答案是6。

　　但如果序列是[1, 2, 3, 4]，最長的擺動子序列為[1]或[2]或[3]，所以答案是2 ( [1, 2] 或 [1, 3] 或 [1, 4] 或 [2, 3] 或 [2, 4] 或 [3, 4] )。

解題方法：

　　使用貪婪法，貪婪的原則為只要遇到轉折點，也就是下一個值變小或者下一個值變大，則代表符合擺動序列的長度就加1。

　　像下方的狀態機，一開始在BEGIN的狀態，只要值一有變化，則進入到UP或DOWN的狀態。UP/DOWN狀態則持續比對目前的值和下一個值是否有變小/變大，有的話則長度加1。

　　須注意edge case空值或只有1個元素的狀況。

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() < 2){
            return nums.size();
        }
        
        const int BEGIN = 0;
        const int UP = 1;
        const int DOWN = 2;
        int curState = BEGIN;
        int maxLength = 1;
        for(int i = 1;i < nums.size() ; ++i){
            switch(curState){
                case BEGIN:
                    if(nums[i-1] > nums[i]){
                        curState = DOWN;
                        maxLength++;
                    }
                    else if(nums[i-1] < nums[i]){
                        curState = UP;
                        maxLength++;
                    }
                    break;
                case UP:
                    if(nums[i-1] > nums[i]){
                        curState = DOWN;
                        maxLength++;
                    }
                    break;
                case DOWN:
                    if(nums[i-1] < nums[i]){
                        curState = UP;
                        maxLength++;
                    }
                    break;
            }
        }
        
        return maxLength;
    }
};

int main()
{
    Solution s;
	vector<int> nums{1,17,5,10,13,15,10,5,16,8}; 
    cout << s.wiggleMaxLength(nums) << endl;

    return 0;
}

using System;

namespace LeetCode376
{
    public class Solution {
        const int BEGIN = 0;
        const int UP = 1;
        const int DOWN = 2;
        public int WiggleMaxLength(int[] nums) {
            if(nums.Length < 2){
                return nums.Length;
            }
            
            int curState = BEGIN;
            int maxLength = 1;
            for(int i = 1;i < nums.Length ; ++i){
                switch(curState){
                    case BEGIN:
                        if(nums[i-1] > nums[i]){
                            curState = DOWN;
                            maxLength++;
                        }
                        else if(nums[i-1] < nums[i]){
                            curState = UP;
                            maxLength++;
                        }
                        break;
                    case UP:
                        if(nums[i-1] > nums[i]){
                            curState = DOWN;
                            maxLength++;
                        }
                        break;
                    case DOWN:
                        if(nums[i-1] < nums[i]){
                            curState = UP;
                            maxLength++;
                        }
                        break;
                }
            }
            
            return maxLength;
            
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[]{1,17,5,10,13,15,10,5,16,8};
            Console.WriteLine(new Solution().WiggleMaxLength(nums));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/300-399/376.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/300-399/376.cs